package com.liunian.algorithmstudy.monotonicstack;

import java.util.Map;
import java.util.Stack;

public class LargestRectangleArea84 {

	/**
	 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
	 求在该柱状图中，能够勾勒出来的矩形的最大面积。



	 示例 1:
	 输入：heights = [2,1,5,6,2,3]
	 输出：10
	 解释：最大的矩形为图中红色区域，面积为 10

	 示例 2：
	 输入： heights = [2,4]
	 输出： 4
	 */
	public int largestRectangleArea(int[] heights) {
		int[] newHeights = new int[heights.length + 2];
		System.arraycopy(heights, 0, newHeights, 1, heights.length);
		Stack<Integer> stack = new Stack<>();
		stack.push(0);
		int res = 0;
		for (int i = 1; i < newHeights.length; i++) {
			while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
				Integer pop = stack.pop();
				if (!stack.isEmpty()) {
					int h = newHeights[pop];
					int w = i - stack.peek() - 1;
					res = Math.max(res, h * w);
				}
			}
			stack.push(i);
		}
		return res;
	}

	public static void main(String[] args) {
		LargestRectangleArea84 largestRectangleArea84 = new LargestRectangleArea84();
		System.out.println(largestRectangleArea84.largestRectangleArea(new int[]{2,1,5,6,2,3}));
	}

}
